//
// Created by ROG on 2024/10/30.
//
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

// 定义节点结构
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// 定义栈结构
typedef struct {
    Node* top;  // 栈顶指针
    int size;   // 栈中元素数量
} Stack;

// 创建栈
Stack* createStack() {
    Stack* s = (Stack*)malloc(sizeof(Stack));
    if (s == NULL) {
        printf("内存分配失败，无法创建栈！\n");
        return NULL;
    }
    s->top = NULL;
    s->size = 0;
    return s;
}

// 判断栈是否为空
int isEmpty(Stack* s) {
    return s->size == 0;
}

// 入栈操作
void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("内存分配失败，无法入栈！\n");
        return;
    }
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
    s->size++;  // 更新栈大小
}

// 出栈操作
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空，无法出栈！\n");
        return -1; // 错误返回值
    }
    Node* temp = s->top;
    int value = temp->data;
    s->top = s->top->next;
    free(temp);
    s->size--;  // 更新栈大小
    return value;
}

// 获取栈顶元素
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("栈为空，无法获取栈顶元素！\n");
        return -1; // 错误返回值
    }
    return s->top->data;
}

// 获取栈的大小
int stackSize(Stack* s) {
    return s->size;
}

// 销毁栈
void destroyStack(Stack* s) {
    while (!isEmpty(s)) {
        pop(s);
    }
    free(s);
    printf("stack has been destroyed\n");
}

void decimalToOct(int decimal) {
    Stack *s = createStack();

    // 将十进制数转换为二进制并存入栈
    while (decimal > 0) {
        int remainder = decimal % 8;
        push(s, remainder);
        decimal /= 8;
    }

    // 输出栈中的二进制数
    printf(":");
    while (!isEmpty(s)) {
        printf("%d", pop(s));
    }
    printf("\n");

    destroyStack(s);
}

int binaryToDecimal(const char* binary) { // 1010
    Stack *s = createStack();

    // 将二进制字符串的每一位压入栈
    for (int i = 0; binary[i] != '\0'; i++) {
        push(s, binary[i] - '0');  // 将字符转为整数并压入栈
    }

    int decimal = 0;
    int position = 0;

    // 从栈中弹出每一位并计算十进制
    while (!isEmpty(s)) {
        int bit = pop(s);
        decimal += bit * pow(2, position);  // 2 的 position 次幂
        position++;
    }

    return decimal;
}

// 用栈实现阶乘
int factorialUsingStack(int n) {
    Stack * s = createStack();

    int result = 1;

    // 模拟递归，将数字逐个入栈
    for (int i = 1; i <= n; i++) {
        push(s, i);
    }

    // 逐个出栈并计算
    while (!isEmpty(s)) {
        result *= pop(s);
    }

    destroyStack(s);

    return result;
}

// 测试链式栈操作
int main() {
    int decimal = 159;
    printf("Dec %d to Oct: ", decimal);
    decimalToOct(decimal);

    const char* binary = "1010";
    printf("Bin %s to Dec: %d\n", binary, binaryToDecimal(binary));

    int n = 5;
    printf("The factorial of %d is %d\n", n, factorialUsingStack(n));

    return 0;
}
